#ifndef STX_ALGORITHM_PARTITION_POINT_HPP
#define STX_ALGORITHM_PARTITION_POINT_HPP

#include <stx/algorithm/common.hpp>

namespace stx {

template<class ForwardIterator, class Predicate>
inline ForwardIterator
partition_point(ForwardIterator first, ForwardIterator last, Predicate pred)
{
    typedef typename std::iterator_traits<ForwardIterator>::difference_type difference_type;
    difference_type len = stx::distance(first, last);
    while (len != 0) {
        difference_type l2 = len / 2;
        ForwardIterator m = first;
        stx::advance(m, l2);
        if (pred(*m)) {
            first = ++m;
            len -= l2 + 1;
        } else {
            len = l2;
        }
    }
    return first;
}

} // namespace stx

#endif // STX_ALGORITHM_PARTITION_POINT_HPP
